import math
import sys


def left(i):

    return 2*i

def right(i):

    return 2*i+1

def max_heapify(A, i):

    global heapsize

    l = left(i)

    r = right(i)   

    if l <= heapsize-1 and A[l] > A[i]:

        largest = l    

    else:

        largest = i

    if r <= heapsize and A[r] > A[largest]:

        largest = r

        

    if largest != i:

        A[i], A[largest] = A[largest], A[i]

        max_heapify(A, largest)



def build_max_heap(A): 

    for i in reversed(range(0, (int(math.floor(len(A)/2))))):

        max_heapify(A, i)



def heapsort(A):

    global heapsize

    heapsize = len(A)-1

    build_max_heap(A)

    for i in reversed(range(0, len(A))):

        A[0], A[i] = A[i], A[0]

        heapsize = heapsize - 1

        max_heapify(A, 0)



A = [1,6,9,8,7,5,2,4,3]

print A

heapsort(A)

print A

